package lib

//link to 698
func init() {
	Probs = append(Probs, Problem{
		Num:         416,
		Discription: "是否能分割成等和子集",
		Level:       2,
		Labels: map[string]int{
			"动态规划":  1,
			"0-1背包": 1,
		},
	})
}

//问题转化：能否从数组中选出一些数使得它们的和为全体和的一半
func CanPartition(nums []int) bool {
	n := len(nums)
	sum := 0
	maxVal := 0
	for i := range nums {
		sum += nums[i]
		maxVal = max(maxVal, nums[i])
	}
	if sum%2 != 0 || maxVal > sum/2 {
		return false
	}
	target := sum / 2

	//dp[i][j]表示nums[:i+1]中能否选出一些数使得它们的和为j
	dp := make([][]bool, n)
	for i := range dp {
		dp[i] = make([]bool, target+1)
		dp[i][0] = true
		dp[0][nums[0]] = true
	}

	for i := 1; i < n; i++ {
		for j := 1; j <= target; j++ {
			if nums[i] == j {
				dp[i][j] = true
				continue
			}

			if nums[i] < j {
				dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i]]
			} else {
				dp[i][j] = dp[i-1][j]
			}
		}
	}

	return dp[n-1][target]
}
